package threshold;

import java.util.Arrays;

/**
 * @Author wujiaming
 * @Description TODO
 * @Date 2023-02-04 20:30
 * @Version 1.0
 * 给你一个按 非递减顺序 排序的整数数组 nums，返回 每个数字的平方 组成的新数组，要求也按 非递减顺序 排序。
 */
public class SortedSquares {


    public int[] sortSquares(int[] nums) {
        for (int i = 0; i < nums.length; i++) {
            nums[i] = (int)Math.pow(nums[i],2);
        }
        //快速排序
        quickSort(nums,0,nums.length-1);
        return nums;
    }

    /**
     * 快速排序
     * @param nums
     * @param low
     * @param high
     */
    void quickSort(int[] nums,int low,int high){
        if(low<high){
            int pos = partition(nums,low,high);
            quickSort(nums,low,pos-1);
            quickSort(nums,pos+1,high);
        }

    }

    public int partition(int[] nums,int low,int high){
        int pivot = nums[low];
        while(low<high){
            while(low<high && nums[high]>=pivot){high--;}
            nums[low]= nums[high];

            while(low<high && nums[low]<=pivot) {low++;}
            nums[high] = nums[low];
        }
        nums[low] = pivot;
        return low;
    }

    public static void main(String[] args) {
        int[] nums = {-7,-3,2,3,11};
        SortedSquares sortedSquares = new SortedSquares();
        System.out.println(Arrays.toString(sortedSquares.sortSquares(nums)));
    }
}
